package com.wc.alorithm_blue_bridge._数据结构.ST.Q1205;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * @Author congge
 * @Date 2023/11/5 12:58
 * @description 区间最大值
 * https://www.lanqiao.cn/problems/1205/learning/?page=2&first_category_id=1&sort=students_count&second_category_id=8
 */
public class Main {
    public static void main(String[] args) {
        Input sc = new Input();
        int n = sc.nextInt();
        int q = sc.nextInt();
        int[] array = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            array[i] = sc.nextInt();
        }
        int k = log2(n);
        // F[i][j] 代表array[i] 到 array[i + 2 ^ j - 1] 之间的最大值
        int[][] F = createST(array);


        StringBuffer ans = new StringBuffer();
        while (q-- > 0) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            ans.append(queryST(F,l,r));
            ans.append('\n');
        }
        System.out.print(ans);
    }

    public static int[][] createST(int[] array) {
        int n = array.length;
        int k = log2(n - 1);
        int[][] F = new int[n][k + 1];

        for (int i = 1; i < n; i++) {
            F[i][0] = array[i];
        }
        for (int j = 1; j <= k; j++) {
            for (int i = 1; i <= n - (1 << j); i++) {
                F[i][j] = Math.max(F[i][j - 1], F[i + (1 << (j - 1))][j - 1]);
            }
        }
        return F;
    }

    public static int queryST(int[][] F, int l, int r) {
        int k = log2(r - l + 1);
        return Math.max(F[l][k], F[r - (1 << k) + 1][k]);
    }

    public static int log2(int n) {
        return (int) (Math.log(n) / Math.log(2));
    }

    static class Input {
        public StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public int nextInt() {
            try {
                in.nextToken();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return (int) in.nval;
        }
    }
}
